POJ1201 Intervals <差分约束系统>

Problem

Intervals

Description

You are given closed, integer intervals and integers .
Write a program that:
reads the number of intervals, their end points and integers from the standard input, computes the minimal size of a set of integers which has at least common elements with interval , for each , writes the answer to the standard output.

Input

The first line of the input contains an integer () – the number of intervals. The following n lines describe the intervals. The line of the input contains three integers , and separated by single spaces and such that and .

Output

The output contains exactly one integer equal to the minimal size of set sharing at least elements with interval , for each .

Sample Input

Sample Output

标签：差分约束系统

Translation

给出个区间，试确定一个集合使得对于，第个区间内至少有个数，并使得此集合尽量小，输出最小大小。

Solution

首先用前缀和。表示从到中共选出多少个数到集合中。这样对于集合，有，于是我们可以从点到连一条权值为的边。因为题意是要满足所有的边，所以我们需要找最长路。
此题有一些细节问题。首先，找最长路需要起点和终点，我们需要找到这些集合覆盖的范围，即找到左端点（其实应该是左端点）的最小值和右端点的最大值，找到的最大值。此外，光有上述的那些边时无法构成一个连通图的，所以我们需要找一些隐含条件。可以发现有，，为了保持一致，应将后面的式子转化为大于等于，即，这样对于，从到连接一条权值为的路，从到连接一条权值为的路，之后就可以直接用找最长路了。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX_N 50000
using namespace std;
int n, cnt, s, t, pre[MAX_N+5], dis[MAX_N+5];
struct node {int v, c, nxt;} E[MAX_N*3+5];
void insert(int u, int v, int c) {
    E[++cnt].v = v, E[cnt].c = c;
    E[cnt].nxt = pre[u], pre[u] = cnt;
}
void SPFA() {
    queue <int> que;
    bool inque[MAX_N+5];
    memset(dis, 128, sizeof(dis));
    memset(inque, 0, sizeof(inque));
    dis[s] = 0;
    que.push(s), inque[s] = true;
    while (!que.empty()) {
        int u = que.front();
        for (int i = pre[u]; i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (dis[u]+c > dis[v]) {
                dis[v] = dis[u]+c;
                if (!inque[v])	que.push(v), inque[v] = true;
            }
        }
        que.pop(), inque[u] = false;
    }
}
int main() {
    while (scanf("%d", &n) != EOF) {
        cnt = 0, s = 50000, t = 0;
        memset(pre, 0, sizeof(pre));
        memset(E, 0, sizeof(E));
        for (int i = 0; i < n; i++) {
            int u, v, c;
            scanf("%d%d%d", &u, &v, &c);
            insert(u, v+1, c);
            s = min(s, u);
            t = max(t, v+1);
        }
        for (int i = s; i < t; i++)	insert(i, i+1, 0), insert(i+1, i, -1);
        SPFA();
        printf("%d\n", dis[t]);
    }
    return 0;
}